#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>

#include "debug.h"
#define DEBUG 0

#include "ht.h"

// The table contains a pointer to an array of linkedlist of ht_node.
struct ht_table {
	// the number of elements in this table
	unsigned int size;

	// the size of the tab.
	unsigned int tab_size;

	ll_list** tab;
};


// ht_node contains a char *, which is the key of this node,
typedef struct ht_node ht_node;
struct ht_node {
	char *key;
	void *data;
};

// Declare private functions
unsigned int ht_hash(ht_table* ht, char const* str);
ht_node* ht_get_node(ht_table *ht, char const* key);
ll_list* ht_get_bucket(ht_table *ht, char const* key);
ht_node* ht_search_bucket(ll_list *ll, char const* key);
void ht_delete_node(ht_node* n);

ht_table* ht_create() {
	ht_table* new = (ht_table*)malloc(sizeof(ht_table));
	new->tab_size = 1024;

	size_t btab_size = sizeof(ll_list*) * new->tab_size;
	new->tab = (ll_list**)malloc(btab_size);
	memset(new->tab, 0, btab_size);

	new->size = 0;
	return new;
}

ht_node* ht_create_node(char const* key, void *data) {
	ht_node* new = (ht_node*)malloc(sizeof(ht_node));

	new->key = (char *)malloc(sizeof(char)*(strlen(key) + 1));
	strcpy(new->key, key);

	new->data = data;

	return new;
}

void* ht_set(ht_table* ht, char const* key, void* data) {
	/* printf("Adding %s: %p\n", key, data); */
	ll_list* ll = (ll_list*)ht_get_bucket(ht, key);
	void *olddata = NULL;
	if (ll == NULL) {
		/* printf("Adding new bucket\n"); */
		ht->tab[ht_hash(ht, key)] = ll = ll_create();
	}

	ht_node* node = ht_search_bucket(ll,key);
	if (node) {
		/* printf("Found old node, replacing\n"); */
		olddata = node->data;
		node->data = data;
	} else {
		/* printf("Creating new node\n"); */
		node = ht_create_node(key, data);
		ll_push(ll, node);
	}

	return olddata;
}

void* ht_get(ht_table* ht, char const* key) {
	ht_node* node = ht_get_node(ht, key);
	return node ? node->data : NULL;
}

ll_list* ht_get_keys(ht_table* ht) {
    // Slow?
    int i;
    ll_list* res = ll_create();
    for (i = 0; i < ht->tab_size; ++i) {
        ll_list* ll = ht->tab[i];
        if (ll != NULL) {
            ht_node* node;
            int i, size = ll_size(ll);
            for (i = 0; i < size; i++) {
                node = ll_get(ll, i);
                ll_push(res, node->key);
            }
        }
    }
    return res;
}

ll_list* ht_get_values(ht_table* ht) {
    // Slow?
    int i, j;
    ll_list* res = ll_create();
    for (i = 0; i < ht->tab_size; ++i) {
        ll_list* ll = ht->tab[i];
        if (ll != NULL) {
            int j, size = ll_size(ll);
            for (j = 0; j < size; j++) {
                ht_node* node = ll_get(ll, j);
                ll_push(res, node->data);
            }
        }
    }
    return res;
}

ll_list* ht_get_bucket(ht_table *ht, char const* key) {
	return (ll_list*)ht->tab[ht_hash(ht, key)];
}

ht_node* ht_get_node(ht_table *ht, char const* key) {
	ll_list* ll = ht_get_bucket(ht, key);
	return ll ? ht_search_bucket(ll, key) : NULL;
}

ht_node* ht_search_bucket(ll_list *ll, char const* key) {
	ht_node* node;
	int i, size = ll_size(ll);
	/* printf("Bucket size: %d\n", size); */
	for (i = 0; i < size; i++) {
		// Horrible complexity, i need some way of iterating over the contents
		// of a linkedlist
		node = ll_get(ll, i);
		/* printf("%s == %s\n", node->key, key); */
		if (strcmp(node->key, key) == 0) {
			return node;
		}
	}
	return NULL;
}

void ht_delete(ht_table* ht) {
	// Slow?
	int i;
	for (i = 0; i < ht->tab_size; ++i) {
		ll_list* ll = ht->tab[i];
		if (ll != NULL) {
			/* printf(" - bucket: %d\n", i); */
			ht_node* node;
			while (node = ll_pop(ll)) {
				/* printf("   * free node: %p\n", &node); */
				ht_delete_node(node);
			}
			/* printf(" x free bucket: %d\n", i); */
			ll_delete(ht->tab[i]);
		}
	}
	free(ht->tab);
	free(ht);
}

void ht_delete_node(ht_node* n) {
	free(n->key);
	free(n);
}

// TODO: use murmurehash2
unsigned int ht_hash(ht_table* ht, char const* str) {
	int i, hash = 0, len = strlen(str);
	for (i = 0; i < len; ++i) {
		hash += str[i];
	}
	return hash % ht->tab_size;
}
